package problem21_Merge_Two_Sorted_Lists;

public class Solution {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
		}
	}

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode dummy=new ListNode(-1);
		ListNode head1=l1,head2=l2,tail=dummy;
		while(head1!=null&&head2!=null){
			if(head1.val<=head2.val) {tail.next=head1;head1=head1.next;}
			else {tail.next=head2;head2=head2.next;}
			tail=tail.next;
		}
		tail.next=head1==null?head2:head1;
		return dummy.next;
	}
}
